#include <iostream>
#include <assert.h>

struct Node
{
    int _val;
    Node* _next;

    Node(int val) :_val(val), _next(nullptr){}
};

//创建链表
Node* CreateList()
{
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);
    Node* node4 = new Node(4);
    Node* node5 = new Node(5);
    Node* node6 = new Node(6);

    node1->_next = node2;
    node2->_next = node3;
    node3->_next = node4;
    node4->_next = node5;
    node5->_next = node6;

    return node1;
}

Node* CreateList2()
{
    Node* node1 = new Node(1);
    return node1;
}

Node* CreateList3()
{
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);

    node1->_next = node2;
    node2->_next = node3;

    return node1;
}

Node* CreateList4()
{
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);
    Node* node4 = new Node(4);

    node1->_next = node2;
    node2->_next = node3;
    node3->_next = node4;

    return node1;
}

//找倒数第k个节点
Node* FindKToTail(Node* phead, unsigned int k)
{
    if(phead == nullptr || k == 0)
        return nullptr;

    Node* fast = phead;
    Node* slow = phead;

    //fast指针先走k-1个距离
    for(int i = 0; i < k - 1; i++)
    {
        if(fast->_next != nullptr)
            fast = fast->_next;
        //不足k个节点
        else
            return nullptr;
    }

    while(fast->_next != nullptr)
    {
        fast = fast->_next;
        slow = slow->_next;
    }

    return slow;
}

//找到链表的中间节点
Node* FindMindleNode(Node* phead)
{
    if(phead == nullptr)
        return nullptr;
    
    Node* slow = phead;
    Node* fast = phead;

    while(fast->_next != nullptr)
    {
        //快指针走两步
        fast = fast->_next;
        if(fast->_next != nullptr)
            fast = fast->_next;
        //慢指针走一步
        slow = slow->_next;
    }
    return slow;
}

int main()
{
    Node* head = CreateList();
    Node* head2 = CreateList2();
    Node* head3 = CreateList3();
    Node* head4 = CreateList4();
    // std::cout << FindKToTail(head, 1)->_val << std::endl;
    // std::cout << FindKToTail(head, 2)->_val << std::endl;
    // std::cout << FindKToTail(head, 3)->_val << std::endl;
    // std::cout << FindKToTail(head, 4)->_val << std::endl;
    // std::cout << FindKToTail(head, 5)->_val << std::endl;
    // std::cout << FindKToTail(head, 6)->_val << std::endl;
    // std::cout << FindKToTail(head, 7)->_val << std::endl;

    std::cout << FindMindleNode(head)->_val << std::endl;
    std::cout << FindMindleNode(head2)->_val << std::endl;
    std::cout << FindMindleNode(head3)->_val << std::endl;
    std::cout << FindMindleNode(head4)->_val << std::endl;
    return 0;
}